home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / CUGUK / APPLICAT / C034.ZIP / DBQSRT.C < prev    next >
Text File  |  2010-11-01  |  5KB  |  284 lines
  1. /*    SDB - sort routines    */
  2.  
  3. #include "bdscio.h"
  4. #include "dbqdefs.h"
  5.  
  6. struct skey *get_skeys(sptr)
  7.     struct scan *sptr;
  8. {
  9.     struct skey *skeys,*newskey,*lastskey;
  10.  
  11.     skeys = lastskey = NULL;
  12.     while (TRUE) {
  13.         if (db_ntoken() != ID)
  14.             { RETERR(SYNTAX) }
  15.  
  16.         if ((newskey = CALLOC(KEYSIZE)) == NULL)
  17.             { RETERR(INSMEM) }
  18.  
  19.         newskey->sk_next = NULL;
  20.         if (!sfind_attr(sptr,newskey,dbv_tstring)) {
  21.             CFREE(newskey);
  22.             return (NULL);
  23.         }
  24.         if (db_token() == ASCENDING || dbv_token == DESCENDING) {
  25.             newskey->sk_type = dbv_token;
  26.             db_ntoken();
  27.         }
  28.         else
  29.             newskey->sk_type = ASCENDING;
  30.  
  31.         if (lastskey == NULL)
  32.             skeys = newskey;
  33.         else
  34.             lastskey->sk_next = newskey;
  35.         lastskey = newskey;
  36.  
  37.         if (db_token() != ',')
  38.             break;
  39.         db_ntoken();
  40.     }
  41.     return (skeys);
  42. }
  43.  
  44. int *db_sort(fmt,a1,a2,a3,a4,a5,a6,a7,a8,a9)
  45.     char *fmt;
  46. {
  47.     struct scan *sptr1,*sptr2,*sptr3;
  48.     struct skey *skeys;
  49.     int result;
  50. #ifdef DBPI
  51.     if (fmt != NULL)
  52.         db_scan(fmt,a1,a2,a3,a4,a5,a6,a7,a8,a9);
  53. #endif
  54.     result = FALSE;        /* be pessimistic */
  55.     if (db_token() == ID)
  56.         db_ntoken();
  57.     else
  58.         strcpy(dbv_tstring,"current");
  59.     if ((sptr1 = db_ropen(dbv_tstring)) == NULL)
  60.         goto sortex;
  61.     if ((sptr2 = db_ropen(dbv_tstring)) == NULL)
  62.         goto sortx1;
  63. #ifdef QUICKSORT
  64.     if ((sptr3 = db_ropen(dbv_tstring)) == NULL)
  65.         goto sortx2;
  66. #endif
  67.     if (db_ntoken() != BY) {
  68.         dbv_errcode = SYNTAX;
  69.         goto sortx3; }
  70.     if ((skeys = get_skeys(sptr1)) == NULL)
  71.         goto sortx3;
  72.  
  73.     result = dqsort(skeys,sptr1,sptr2,sptr3);
  74.  
  75.     free_skeys(skeys);
  76.  
  77. sortx3:
  78. #ifdef QUICKSORT
  79.     db_rclose(sptr3);
  80. #endif
  81. sortx2:
  82.     db_rclose(sptr2);
  83. sortx1:
  84.     db_rclose(sptr1);
  85. sortex:
  86.     return (result);
  87. }
  88.  
  89. free_skeys(skeys)
  90.     struct skey *skeys;
  91. {
  92.     struct skey *thisskey;
  93.  
  94.     for (thisskey = skeys; skeys != NULL; thisskey = skeys) {
  95.         skeys = skeys->sk_next;
  96.         CFREE(thisskey);
  97.     }
  98. }
  99.  
  100. int sfind_attr(sptr,newskey,aname)
  101.     struct scan *sptr; struct skey *newskey; char *aname;
  102. {
  103.     struct attribute *aptr;
  104.     int i,astart;
  105.     astart = 1;
  106.     for (i = 0; i < NATTRS; i++) {
  107.         aptr = &sptr->sc_relation->rl_header.hd_attrs[i];
  108.  
  109.         if (aptr->at_name[0] == 0)
  110.             break;
  111.  
  112.         if (db_sncmp(aname,aptr->at_name,ANSIZE) == 0) {
  113.             newskey->sk_start = astart;
  114.             newskey->sk_aptr = aptr;
  115.             return (TRUE);
  116.         }
  117.  
  118.         astart += aptr->at_size;
  119.     }
  120.  
  121.     RETERR(ATUNDF)
  122. }
  123.  
  124. int dqsort(skeys,sptr1,sptr2,sptr3)
  125.     struct skey *skeys; struct scan *sptr1,*sptr2,*sptr3;
  126. {
  127.     int passes, swaps;
  128.     int i,j,m,n;
  129.     int rec1,rec2,rec3;
  130.     int k, l, r;    /* orig */
  131.  
  132.     passes = 0; swaps = 0;
  133.  
  134. #ifdef QUICKSORT
  135.  
  136.     rec1 = 0; rec2 = 0; rec3 = 0;
  137.     n = sptr1->sc_relation->rl_tcnt;
  138.     m = n;
  139.  
  140.     while(m>1) {
  141.         passes++;
  142.         if ((m/=3) < 1) m = 1;
  143.         for (j=1; j<=n-m; j++) {
  144.           if (rec1 != j+m) {
  145.             if (!db_rget(sptr1, rec1=j+m)) return (FALSE);
  146.             }
  147.           for (i=j; i>=1; i-=m) {
  148.             if (rec2 != i) {
  149.                 if (!db_rget(sptr2, rec2=i)) return (FALSE);
  150.                 }
  151.             if (scompare(skeys,sptr1,sptr2) > 0)
  152.                 break;
  153.             if (rec3 != i+m) {
  154.                 if (!db_rget(sptr3, rec3=i+m)) return (FALSE);
  155.                 }
  156.             sassign( sptr3, sptr2);
  157.             swaps++;
  158.             }
  159.           if (rec1 != i+m) {
  160.             if (rec3 != i+m) {
  161.                 if (!db_rget(sptr3, rec3=i+m)) return (FALSE);
  162.                 }
  163.             sassign( sptr3, sptr1);
  164.             swaps++;
  165.             }
  166.           }
  167.         }
  168.  
  169. #else
  170. /*    original sort    */
  171.  
  172.     l = 2;
  173.     r = sptr1->sc_relation->rl_tcnt;
  174.     k = r;
  175.  
  176.     do {
  177.         for (j = r; j >= l; j--) {
  178.             if (!db_rget(sptr1,j-1))
  179.                 return (FALSE);
  180.             if (!db_rget(sptr2,j))
  181.                 return (FALSE);
  182.             if (scompare(skeys,sptr1,sptr2) > 0) {
  183.                 sswap(sptr1,sptr2);
  184.                 k = j;
  185.                 swaps++;
  186.             }
  187.         }
  188.         l = k + 1;
  189.         for (j = l; j <= r; j++) {
  190.             if (!db_rget(sptr1,j-1))
  191.                 return (FALSE);
  192.             if (!db_rget(sptr2,j))
  193.                 return (FALSE);
  194.             if (scompare(skeys,sptr1,sptr2) > 0) {
  195.                 sswap(sptr1,sptr2);
  196.                 k = j;
  197.                 swaps++;
  198.             }
  199.         }
  200.         r = k - 1;
  201.         passes++;
  202.     } while (l <= r);
  203.  
  204. #endif
  205.  
  206.     printf("%d swaps in %d passes\n",swaps,passes);
  207.  
  208.     return (TRUE);
  209. }
  210.  
  211. int scompare(skeys,sptr1,sptr2)
  212.     struct skey *skeys; struct scan *sptr1,*sptr2;
  213. {
  214.     struct skey *cskey;
  215.     int result;
  216.     for (cskey = skeys; cskey != NULL; cskey = cskey->sk_next)
  217.         if ((result = cattr(cskey,sptr1,sptr2)) != 0)
  218.             break;
  219.     return (result);
  220. }
  221.  
  222. int cattr(cskey,sptr1,sptr2)
  223.     struct skey *cskey; struct scan *sptr1,*sptr2;
  224. {
  225.     int astart,aend,i;
  226.  
  227.     astart = cskey->sk_start;
  228.     aend = astart + cskey->sk_aptr->at_size;
  229.     for (i = astart; i < aend; i++)
  230.         if (sptr1->sc_tuple[i] != sptr2->sc_tuple[i])
  231.             break;
  232.     if (i == aend)
  233.         return (0);
  234.  
  235.     if (sptr1->sc_tuple[i] < sptr2->sc_tuple[i])
  236.         if (cskey->sk_type == ASCENDING)
  237.             return (-1);
  238.         else
  239.             return (1);
  240.     else
  241.         if (cskey->sk_type == ASCENDING)
  242.             return (1);
  243.         else
  244.             return (-1);
  245. }
  246.  
  247. #ifdef QUICKSORT
  248. int sassign(sptr1,sptr2)
  249.     struct scan *sptr1,*sptr2;
  250. {
  251.     unsigned tnum1, tnum2;
  252.  
  253.     tnum1 = sptr1->sc_atnum;
  254.  
  255.     if (!db_rput(sptr2,tnum1))
  256.         return (FALSE);
  257.     return (TRUE);
  258. }
  259.  
  260. #else
  261.  
  262. int sswap(sptr1,sptr2)
  263.     struct scan *sptr1,*sptr2;
  264. {
  265.     unsigned tnum1, tnum2;
  266.  
  267.     tnum1 = sptr1->sc_atnum;
  268.     tnum2 = sptr2->sc_atnum;
  269.  
  270.     if (!db_rput(sptr1,tnum2))
  271.         return (FALSE);
  272.     if (!db_rput(sptr2,tnum1))
  273.         return (FALSE);
  274.     return (TRUE);
  275. }
  276.  
  277. #endif
  278.  
  279.     if (!db_rput(sptr1,tnum2))
  280.         return (FALSE);
  281.     if (!db_rput(sptr2,tnum1))
  282.         return (FALSE);
  283.     return (TRUE);
  284.